package com.leetcode.algorithm.y22.m07;

import java.util.ArrayList;
import java.util.List;

/**
 * 784. 字母大小写全排列
 * 
 * https://leetcode.cn/problems/letter-case-permutation/
 * 
 * @author jie.deng
 *
 */
class Question0784Solution01 {

	public List<String> letterCasePermutation(String s) {
		List<String> retList = new ArrayList<>();
		StringBuilder builder = new StringBuilder();
		letterCasePermutation(0, builder, s, retList);
		return retList;
	}

	private void letterCasePermutation(int level, StringBuilder builder, String s, List<String> retList) {
		int len = s.length();
		// 递归终止条件
		if (level == len) {
			retList.add(builder.toString());
			return;
		}

		// 当前层逻辑
		char ch = s.charAt(level);
		if (ch <= '9') {
			// 当前层逻辑
			builder.append(ch);
			// 递归调用下一层
			letterCasePermutation(level + 1, builder, s, retList);
			// 回溯
			builder.deleteCharAt(level);
		} else {
			char[] arr = new char[2];
			arr[0] = ((ch >= 'a') ? ch : (char) (ch - 'A' + 'a'));
			arr[1] = (char) (arr[0] - 'a' + 'A');
			for (int i = 0; i < 2; i++) {
				// 当前层的选择
				ch = arr[i];
				// 当前层逻辑
				builder.append(ch);
				// 递归调用下一层
				letterCasePermutation(level + 1, builder, s, retList);
				// 恢复状态，继续下一个选择
				builder.deleteCharAt(level);
			}
		}
	}

}